package org.basis.algorithm.promote;

import java.util.ArrayDeque;

/**
 * KMP算法
 * kmp算法解决的其实就是Java代码中的String.indexOf(xx)
 * 即给你两个字符串str1和str2，判断str1中是否包含str2，如果包含请返回str2在str1中的起始下标
 *
 * @author Mr_wenpan@163.com 2022/01/05 16:34
 */
public class KMP {

    public static void main(String[] args) {

    }

    public String simplifyPath(String path) {
        String[] names = path.split("/");
        // 基于数组实现的双端队列来表示栈
        ArrayDeque<String> deque = new ArrayDeque<>();
        for (String name : names) {
            if ("..".equals(name)) {
                // 如果栈不为空，则从尾部拿一个元素出来
                if (!deque.isEmpty()) {
                    deque.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                // 合法的字符串入栈（从队列尾部加入）
                deque.addLast(name);
            }
        }

        // 如果没有解析出有用的路径
        if (deque.isEmpty()) {
            return "/";
        }
        StringBuilder builder = new StringBuilder();
        while (!deque.isEmpty()) {
            // 从双端队列前面拿（此时双端队列不在被当栈用，而是当做队列使用）
            builder.append("/").append(deque.pollFirst());
        }

        return builder.toString();
    }

    /**
     * 使用KMP算法加速后的方法
     */
    public static int getIndexOf(String str1, String str2) {
        if (str1 == null || str2 == null || str2.length() < 1 || str1.length() < str2.length()) {
            return -1;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int idx1 = 0;
        int idx2 = 0;
        int[] next = getNextArray(chars2);
        while (idx1 != chars1.length && idx2 != chars2.length) {
            if (chars1[idx1] == chars2[idx2]) {
                idx1++;
                idx2++;
            } else if (next[idx2] == -1) {
                idx1++;
            } else {
                idx2 = next[idx2];
            }
        }

        if (idx2 >= chars2.length) {
            return idx2 - idx1;
        }

        return -1;
    }

    public static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.length) {
            if (ms[i - 1] == ms[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

    /**
     * 经典的方法，该方法时间复杂度较高，但是很容易想到和实现
     */
    public static int getIndexOf2(String str1, String str2) {
        if (str1 == null || str1.isEmpty() || str1.length() < str2.length()) {
            return -1;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int idx1 = 0;
        int idx2 = 0;

        // 逐个位置比较，时间复杂度O（N * M）
        for (int i = 0; i < chars1.length; i++) {
            idx1 = i;
            idx2 = 0;
            while (idx1 < chars1.length && idx2 < chars2.length && chars1[idx1] == chars2[idx2]) {
                idx1++;
                idx2++;
            }
            // 比较完后，如果idx2到达了末尾，那么说明找到了，反之则说明没找到
            if (idx2 >= chars2.length) {
                return idx1 - idx2;
            }
        }

        return -1;
    }
}
